#include "test_tools.h"
#include <cds/hash.h>
#include <cds/hash_table.h>

#define HASH_BUCKET_NUM 128

struct test_hlist_node {
    struct hlist_node list;
    unsigned long key;
};

/* 计算哈希值的函数。 */
static unsigned long __htable_hash_func(unsigned long key)
{
    return hash_64(key, sizeof(unsigned long) << 3);
}

/* 对比两个哈希节点键值大小关系的函数。 */
static int __htable_cmp_func(unsigned long key1, unsigned long key2)
{
    if (key1 > key2) {
        return 1;
    } else if (key1 < key2) {
        return -1;
    }
    return 0;
}

/* 获得一个哈希节点键值的函数。 */
static unsigned long __htable_get_key_func(struct hlist_node *node)
{
    return container_of(node, struct test_hlist_node, list)->key;
}

static struct hash_table_opts __htab_opts = {
    .hash_func = __htable_hash_func,
    .cmp_func = __htable_cmp_func,
    .get_key_func = __htable_get_key_func
};

static inline struct test_hlist_node *CREATE_HASH_NODE(unsigned long key)
{
    struct test_hlist_node *node = malloc(sizeof(struct test_hlist_node));
    if (node != NULL) {
        init_hash_node(&node->list);
        node->key = key;
    }
    return node;
}

/* 尝试创建一个键值的节点并插入哈希表。 */
static inline int insert_one_key(
    struct hash_table *htab,
    char *in_table_marks,
    unsigned long key,
    unsigned long array_length,
    int replace
)
{
    if (key >= array_length) {
        LOG_TEST_FAIL("key value is too big. key: %lu\n", key);
        return -1;
    }
    struct test_hlist_node *new_node = CREATE_HASH_NODE(key);
    if (new_node == NULL) {
        LOG_TEST_FAIL("failed to create node. key: %lu\n", key);
        return -1;
    }
    struct hlist_node *inserted = insert_hash_node(htab, &new_node->list, replace);
    if (inserted == NULL) {
        LOG_TEST_FAIL("failed to insert new node. key: %lu\n", key);
        return -1;
    }
    if (inserted != &new_node->list) {
        free(container_of(inserted, struct test_hlist_node, list));
        if (!replace) {
            LOG_TEST_FAIL("the node inserted is node the one just created!\n");
            return -1;
        }
    }
    in_table_marks[key] = 1;
    return 0;
}

/* 尝试从哈希表中删除一个键值的节点。 */
static inline int delete_one_key(
    struct hash_table *htab,
    char *in_table_marks,
    unsigned long key,
    unsigned long array_length
)
{
    if (key >= array_length) {
        LOG_TEST_FAIL("key value is too big. key: %lu\n", key);
        return -1;
    }
    struct hlist_node *node_del = del_key_hash_node(htab, key);
    if (node_del == NULL) {
        LOG_TEST_FAIL("failed to delete node. key: %lu\n", key);
        return -1;
    }
    in_table_marks[key] = 0;
    free(container_of(node_del, struct test_hlist_node, list));
    return 0;
}

/**
 * @brief 对一个哈希表进行完整的检验。
 */
static inline int validate_hash_table(
    struct hash_table *htab,
    unsigned long *test_array,
    unsigned long array_length,
    char *in_table_marks
)
{
    unsigned long node_count = 0;
    struct hlist_node *node = NULL;
    for (unsigned long i = 0; i < array_length; i++) {
        node = find_key_hash_node(htab, test_array[i]);
        if (node == NULL && in_table_marks[test_array[i]] != 0) {
            LOG_TEST_FAIL(
                "i: %lu. node with key: %lu is not found in hash table, "
                "but the key was marked in 'in_table_marks'.\n",
                i,
                test_array[i]
            );
            return -1;
        }
        if (node != NULL) {
            if (in_table_marks[test_array[i]] == 0) {
                LOG_TEST_FAIL(
                    "i: %lu. node with key: %lu is found in hash table, "
                    "but the key was not marked in 'in_table_marks'.\n",
                    i,
                    test_array[i]
                );
                return -1;
            }
            if (__htable_get_key_func(node) != test_array[i]) {
                LOG_TEST_FAIL(
                    "i: %lu. node with key: %lu is found in hash table, "
                    "but the key was not the given one: %lu.\n",
                    i,
                    test_array[i],
                    __htable_get_key_func(node)
                );
                return -1;
            }
            node_count += 1;
        }
    }
    if (node_count != htab->nums) {
        LOG_TEST_FAIL("node_count: %lu, htab->nums: %lu\n", 
            node_count,
            htab->nums
        );
        return -1;
    }
    return 0;
}

static inline int foreach_hash_node_test(
    struct hash_table *htab,
    unsigned long max_key,
    char *tmp_in_table_marks,
    char *in_table_marks
)
{
    if (htab == NULL || tmp_in_table_marks == NULL || in_table_marks == NULL) {
        LOG_TEST_FAIL(" ");
        return -1;
    }
    if (max_key == 0) {
        LOG_TEST_FAIL(" ");
        return -1;
    }
    memset(tmp_in_table_marks, 0, sizeof(char) * max_key);

    int cnt = 0;
    struct hlist_head *buc;
    struct test_hlist_node *pos;
    struct test_hlist_node *n; 
    htable_foreach_entry_safe(htab, buc, pos, n, list) {
        unsigned long tmp_key = (unsigned long)__htable_get_key_func(&pos->list);
        if (tmp_key >= max_key) {
            LOG_TEST_FAIL("key value is too large!\n");
            return -1;
        }
        if (tmp_in_table_marks[tmp_key] != 0) {
            LOG_TEST_FAIL("more than one node have the same value!\n");
            return -1;
        }
        
        tmp_in_table_marks[tmp_key] = 1;
        cnt++;
    }

    for (unsigned long i = 0; i < max_key; i++) {
        if (!(tmp_in_table_marks[i]) != !(in_table_marks[i])) {
            LOG_TEST_FAIL("in_table_marks donnot fully match!\n");
            printf("i: %lu: mark: %d, tmp mark: %d\n", 
                i,
                in_table_marks[i],
                tmp_in_table_marks[i]
            );
            return -1;
        }
    }
    return 0;
}

int main(void)
{
    unsigned long test_array[] = {
        1733, 1, 671, 2839, 288, 5, 3409, 1099, 2933, 3611, 68, 806, 12, 3472, 1946, 15, 
        2638, 1714, 1907, 19, 1933, 21, 22, 3202, 2528, 25, 2108, 2873, 1458, 3332, 2211, 2571, 
        32, 3104, 34, 35, 2718, 3770, 2257, 1638, 3257, 41, 3085, 43, 2014, 803, 925, 501, 
        1564, 2721, 2422, 51, 52, 53, 2282, 285, 1393, 57, 1210, 59, 3533, 61, 1504, 63, 
        2500, 2176, 66, 67, 2, 788, 2072, 311, 1928, 3406, 74, 1630, 76, 77, 78, 79, 
        3455, 177, 2923, 3047, 3297, 2594, 86, 87, 2338, 2716, 90, 91, 92, 83, 1014, 95, 
        96, 669, 3023, 2194, 100, 101, 3898, 3541, 3729, 2341, 1445, 107, 2167, 3618, 110, 1736, 
        1590, 113, 1523, 775, 3771, 117, 118, 119, 3943, 3438, 3539, 123, 124, 125, 1556, 2924, 
        128, 1158, 2195, 131, 132, 2503, 1462, 135, 136, 2720, 138, 199, 3744, 3025, 580, 143, 
        144, 145, 146, 147, 1045, 149, 150, 151, 2262, 153, 1613, 1622, 156, 3630, 3805, 1454, 
        438, 161, 1582, 1238, 164, 1091, 166, 3962, 2445, 631, 2659, 2971, 755, 1997, 1587, 175, 
        680, 2989, 3678, 179, 3933, 860, 3449, 183, 184, 163, 1314, 1288, 188, 592, 2992, 3837, 
        192, 193, 3492, 1914, 196, 197, 2421, 1574, 2600, 201, 202, 3158, 204, 1588, 1427, 1970, 
        2788, 3772, 210, 211, 6, 213, 2439, 215, 216, 255, 814, 219, 3055, 1498, 1885, 223, 
        1820, 3400, 226, 1727, 3733, 3317, 2901, 3633, 3619, 909, 94, 3133, 236, 2637, 1070, 58, 
        240, 4058, 751, 243, 244, 245, 246, 877, 3286, 1977, 2757, 332, 252, 3072, 254, 1991, 
        3842, 1281, 258, 3262, 260, 1881, 3935, 180, 3370, 265, 1355, 267, 4074, 2938, 3856, 2880, 
        355, 798, 1292, 275, 415, 277, 3739, 279, 1390, 510, 2553, 283, 2080, 3376, 2310, 2407, 
        2507, 289, 3464, 291, 635, 293, 2246, 1161, 296, 297, 298, 1272, 3447, 301, 3190, 303, 
        1304, 305, 306, 3666, 963, 3050, 310, 3685, 3607, 1792, 122, 315, 466, 317, 318, 4009, 
        320, 321, 3707, 323, 729, 325, 326, 327, 1936, 647, 688, 1657, 2951, 3844, 1947, 2909, 
        336, 2948, 3101, 339, 340, 502, 342, 3635, 2601, 1762, 346, 749, 348, 349, 3445, 351, 
        2462, 353, 3815, 854, 2461, 357, 2483, 3535, 360, 1298, 3791, 363, 3850, 365, 429, 2889, 
        368, 537, 392, 371, 70, 1674, 1854, 1841, 1027, 377, 378, 379, 380, 381, 382, 842, 
        3226, 385, 231, 2725, 388, 4085, 174, 391, 1815, 3865, 394, 3405, 2001, 397, 313, 1241, 
        400, 492, 3505, 403, 404, 405, 406, 3485, 408, 409, 2731, 411, 259, 413, 2382, 3487, 
        416, 417, 3568, 419, 420, 105, 422, 423, 424, 1154, 3855, 2761, 65, 1529, 3053, 431, 
        3886, 433, 434, 56, 3135, 437, 3496, 439, 2574, 441, 1228, 3845, 269, 3139, 446, 2898, 
        2691, 449, 453, 578, 2154, 3184, 454, 1033, 2576, 3092, 3693, 522, 2782, 1145, 462, 1522, 
        464, 2326, 2403, 2848, 4078, 1822, 1385, 471, 84, 3122, 3143, 475, 1196, 477, 478, 479, 
        1974, 789, 482, 706, 2728, 3661, 1783, 487, 2306, 3590, 1195, 1236, 3584, 1649, 1036, 916, 
        384, 497, 498, 499, 2087, 1370, 55, 503, 39, 505, 506, 1258, 3218, 467, 1689, 2032, 
        512, 513, 514, 239, 516, 1257, 1419, 1489, 278, 521, 2740, 4038, 524, 3947, 1726, 527, 
        1175, 3011, 1119, 190, 532, 1133, 534, 987, 1696, 3126, 538, 539, 272, 692, 542, 3490, 
        544, 3219, 1230, 946, 548, 3245, 550, 551, 2538, 1441, 3340, 555, 3037, 4069, 558, 3441, 
        1842, 472, 3756, 563, 564, 565, 566, 553, 358, 2688, 570, 571, 3765, 362, 2970, 575, 
        217, 577, 1358, 3004, 682, 2733, 582, 284, 584, 585, 3194, 587, 3116, 589, 185, 504, 
        3830, 2206, 594, 595, 198, 597, 598, 599, 3364, 387, 1206, 603, 518, 3215, 606, 607, 
        2036, 2497, 1706, 3230, 612, 2710, 1518, 615, 616, 579, 3513, 886, 736, 621, 3294, 3326, 
        2506, 625, 626, 618, 2678, 3668, 630, 2466, 632, 1111, 634, 2727, 917, 1922, 638, 639, 
        1781, 641, 3359, 1772, 1893, 645, 646, 1818, 648, 238, 2841, 2648, 2360, 2050, 476, 655, 
        656, 1077, 658, 2161, 1403, 154, 2457, 663, 664, 665, 1442, 667, 668, 2458, 670, 855, 
        1224, 2208, 2111, 2204, 3698, 1213, 678, 2234, 376, 681, 2534, 2684, 2779, 3508, 1784, 687, 
        2712, 689, 676, 1775, 4027, 3224, 1594, 1347, 3110, 697, 2221, 225, 700, 701, 910, 540, 
        704, 705, 986, 2621, 708, 709, 3404, 711, 712, 713, 1382, 2741, 474, 717, 1017, 719, 
        720, 721, 3752, 1973, 724, 725, 1495, 962, 728, 139, 674, 731, 732, 733, 1194, 369, 
        2645, 737, 2790, 1000, 740, 3119, 637, 1937, 744, 691, 396, 747, 748, 4079, 750, 4036, 
        673, 3587, 3142, 261, 442, 757, 758, 1671, 1354, 3278, 530, 3304, 2074, 1105, 1625, 767, 
        836, 769, 770, 1628, 772, 3821, 1429, 366, 2510, 1957, 1995, 779, 3339, 3045, 782, 783, 
        784, 802, 786, 787, 581, 2811, 3345, 791, 2317, 793, 3087, 795, 796, 2092, 1237, 799, 
        649, 801, 2230, 643, 804, 805, 1142, 1910, 1786, 1944, 810, 2305, 812, 3987, 3003, 1766, 
        816, 3148, 960, 361, 2771, 3017, 3282, 221, 824, 825, 3664, 827, 372, 2357, 593, 831, 
        832, 833, 1488, 835, 1895, 2524, 3559, 839, 1377, 3624, 3302, 469, 844, 3031, 2487, 847, 
        3136, 849, 2319, 851, 1096, 1248, 1543, 815, 856, 2343, 858, 2414, 3070, 1079, 862, 1474, 
        3974, 865, 991, 1193, 1300, 869, 870, 871, 1676, 873, 1694, 1968, 876, 972, 878, 2427, 
        3761, 1641, 3892, 883, 672, 1828, 1761, 887, 3314, 889, 890, 891, 892, 330, 525, 895, 
        2803, 897, 898, 1752, 2722, 2251, 902, 903, 3901, 905, 906, 907, 3044, 390, 2417, 911, 
        2711, 913, 914, 915, 4084, 3878, 253, 1278, 535, 921, 922, 2034, 924, 282, 926, 2217, 
        3366, 929, 930, 998, 932, 2207, 934, 935, 845, 937, 879, 2057, 3123, 3152, 1882, 108, 
        1666, 1966, 2104, 947, 3582, 1276, 950, 2397, 952, 461, 3010, 1519, 956, 300, 4088, 335, 
        4017, 961, 509, 3948, 3315, 965, 3252, 2964, 690, 969, 2920, 872, 853, 2906, 974, 2314, 
        1496, 2226, 2058, 2959, 2131, 981, 2025, 3498, 984, 1407, 1870, 1339, 3427, 989, 990, 2605, 
        992, 993, 994, 995, 3687, 2561, 2393, 999, 2172, 3008, 3511, 1003, 1661, 2183, 3857, 1007, 
        1212, 13, 1010, 1011, 1031, 2038, 2489, 1015, 1016, 1406, 3868, 2546, 1020, 3700, 1152, 3973, 
        1527, 1025, 1889, 2112, 1028, 1135, 3801, 2990, 1032, 4083, 1034, 2021, 1239, 4028, 1703, 1039, 
        1912, 1041, 1042, 1043, 1044, 1023, 2639, 1915, 3329, 2590, 1050, 1051, 1214, 1053, 186, 3319, 
        1056, 106, 1058, 1864, 1060, 2879, 1062, 1738, 2781, 1065, 1066, 3681, 1068, 3743, 3118, 1929, 
        1633, 500, 1074, 1075, 1913, 170, 1078, 3488, 3964, 241, 1082, 191, 3353, 4007, 1086, 1087, 
        1100, 157, 4008, 3910, 220, 1093, 1094, 1095, 2498, 116, 763, 1722, 3330, 1376, 3596, 1364, 
        3799, 42, 1106, 1107, 2039, 1109, 1567, 4030, 1112, 3273, 1305, 1336, 2289, 1117, 1118, 1837, 
        840, 2145, 1122, 2186, 214, 1484, 295, 1127, 2064, 1129, 1130, 971, 820, 2942, 1134, 2730, 
        3453, 1137, 1138, 3028, 1952, 1141, 843, 1143, 3979, 228, 1146, 1813, 1286, 1149, 1150, 178, 
        1580, 1153, 1271, 1155, 1156, 1157, 3604, 1159, 1160, 1563, 328, 1163, 1164, 1165, 3465, 1167, 
        1168, 557, 1170, 1022, 4066, 2073, 1174, 1589, 1176, 2459, 2366, 1179, 457, 2690, 1182, 1088, 
        1184, 1185, 1186, 3876, 3187, 949, 1190, 975, 1192, 3240, 3953, 2842, 294, 1197, 1198, 375, 
        2059, 3394, 2613, 1203, 1204, 1887, 2091, 1207, 1208, 1357, 1812, 3757, 596, 1654, 3478, 2517, 
        1216, 1217, 2596, 1219, 1220, 1221, 2694, 1223, 3180, 1225, 1814, 977, 1845, 970, 273, 354, 
        1232, 3679, 1234, 1235, 73, 2413, 3161, 2819, 1240, 734, 1242, 1243, 1244, 1245, 1246, 3363, 
        1110, 1249, 1838, 4077, 2827, 1253, 1476, 1255, 1256, 3683, 2532, 1131, 1827, 2078, 3014, 1900, 
        3835, 1265, 1266, 1140, 1268, 440, 2120, 2663, 3951, 1273, 1274, 1275, 3869, 3507, 1725, 1279, 
        1126, 951, 875, 2860, 2520, 3716, 3374, 1287, 3810, 1984, 1264, 1291, 2236, 364, 936, 1295, 
        1296, 2687, 3516, 3109, 1755, 1301, 1302, 1780, 1024, 3362, 1306, 1307, 1308, 1309, 2391, 1340, 
        861, 1313, 2802, 3061, 1316, 1317, 1318, 2026, 1320, 1321, 1322, 3204, 868, 3665, 1326, 1327, 
        1328, 2540, 2023, 1331, 1332, 1373, 452, 1335, 3567, 1337, 1338, 187, 3275, 2200, 2676, 2491, 
        1344, 1345, 4, 3741, 256, 654, 2777, 3223, 1352, 2224, 2350, 2301, 2776, 3575, 111, 1359, 
        3328, 3826, 3793, 1363, 3182, 1365, 837, 1367, 3040, 1369, 2267, 2935, 2052, 4056, 3631, 2921, 
        3674, 3904, 1378, 1794, 1380, 1381, 3372, 1855, 1384, 4050, 1386, 3470, 1388, 2812, 2569, 46, 
        2259, 4053, 60, 1395, 1396, 2796, 2016, 1072, 1719, 1401, 1402, 2519, 1404, 1405, 3927, 1695, 
        3256, 1409, 823, 1411, 1832, 1413, 1434, 1415, 3075, 2886, 1418, 1799, 1420, 1421, 1422, 1619, 
        1424, 1425, 1227, 1277, 1428, 37, 3421, 1431, 1835, 2658, 576, 1391, 93, 1250, 2999, 1439, 
        194, 3803, 2916, 1443, 2086, 2707, 1446, 2896, 1448, 1449, 1746, 1451, 526, 1685, 3481, 979, 
        1456, 1457, 2917, 1459, 1460, 1461, 3020, 3782, 4092, 3476, 3397, 554, 1468, 1469, 4003, 768, 
        1472, 209, 1750, 1259, 3172, 2609, 1478, 3980, 1480, 2387, 1482, 1483, 3147, 1485, 1486, 3475, 
        2147, 2401, 1490, 1491, 3018, 1493, 614, 1101, 3988, 4024, 3391, 2526, 559, 1501, 1502, 1503, 
        62, 4062, 1506, 1507, 718, 1509, 1510, 1046, 1054, 1513, 1514, 1515, 1516, 1517, 1169, 3577, 
        1520, 3114, 1201, 3446, 1524, 2179, 1526, 2755, 1151, 1763, 3071, 515, 1532, 1533, 1534, 1535, 
        723, 3614, 773, 2641, 569, 1444, 2399, 1055, 1188, 1545, 3198, 2646, 2599, 1549, 181, 329, 
        684, 1398, 2411, 1555, 583, 3673, 1558, 1559, 1560, 3578, 3369, 1798, 1537, 1565, 1566, 696, 
        3956, 1569, 944, 3385, 1572, 556, 316, 1575, 2190, 2620, 738, 484, 2715, 1713, 2875, 572, 
        103, 1585, 2051, 3728, 822, 543, 894, 2372, 1592, 1593, 3609, 1595, 3248, 2316, 3887, 1599, 
        1600, 1601, 1906, 1603, 1604, 1083, 1606, 1607, 1608, 1609, 69, 4020, 36, 3523, 1614, 1615, 
        3280, 1617, 2996, 2900, 1591, 1621, 3221, 1623, 89, 807, 1626, 3277, 2324, 1629, 1252, 3786, 
        3063, 463, 1319, 468, 1636, 1637, 1389, 1639, 1640, 904, 1642, 1643, 3626, 1645, 1412, 1148, 
        1648, 2859, 2079, 1651, 3131, 1653, 2943, 2693, 3417, 1018, 1658, 1659, 1660, 2748, 1064, 1663, 
        1664, 1742, 3084, 2683, 1668, 1851, 1670, 3065, 1884, 1800, 3787, 900, 1777, 826, 1678, 997, 
        1680, 1521, 1682, 3547, 1684, 3419, 1686, 2570, 3079, 2820, 3702, 2797, 1073, 819, 2428, 2612, 
        314, 2203, 1698, 2003, 1700, 852, 1702, 2918, 1704, 1705, 3013, 1707, 1708, 1816, 1710, 1366, 
        3950, 1035, 1371, 1715, 1716, 3655, 1718, 850, 1720, 2085, 3781, 1723, 1724, 528, 2805, 1497, 
        1728, 1729, 2438, 3858, 1584, 942, 1734, 1735, 142, 943, 18, 1904, 1570, 1741, 350, 1743, 
        1744, 1745, 3181, 1747, 1748, 1749, 2298, 1751, 3656, 1753, 2494, 2334, 1756, 1757, 1758, 1759, 
        2448, 1071, 3030, 1732, 31, 3439, 2591, 395, 1768, 4051, 3491, 1771, 666, 1280, 1774, 242, 
        2745, 1999, 389, 1779, 745, 1085, 2518, 2872, 2907, 754, 2355, 2504, 1788, 771, 1790, 1791, 
        3243, 1793, 212, 1795, 1796, 1536, 1294, 428, 3982, 1801, 2158, 1803, 137, 1805, 460, 1807, 
        1808, 1809, 1810, 1811, 3228, 4018, 2367, 33, 292, 2102, 3644, 2563, 3105, 1821, 1222, 1787, 
        3145, 205, 3709, 1330, 1453, 99, 1830, 2817, 1350, 2647, 1834, 2629, 1836, 450, 507, 1839, 
        1840, 785, 1477, 1843, 1844, 3082, 1846, 271, 1848, 1849, 1850, 2101, 120, 1853, 1789, 3625, 
        1333, 1857, 1858, 1859, 1860, 1861, 2852, 2689, 3961, 790, 1866, 3818, 1868, 4035, 2409, 3132, 
        1785, 1873, 1874, 1173, 1876, 792, 1878, 1879, 1579, 3766, 3599, 4068, 270, 1553, 2344, 3873, 
        1888, 3959, 1890, 3175, 1892, 2342, 1894, 2749, 3380, 1897, 1898, 1899, 1896, 908, 1902, 1903, 
        112, 1905, 2704, 622, 1908, 1909, 3824, 1911, 426, 982, 3848, 1323, 794, 1917, 2592, 567, 
        1008, 1528, 3649, 1923, 1924, 3124, 2840, 2307, 1823, 1550, 1930, 761, 331, 2089, 1934, 1935, 
        650, 586, 1938, 1939, 3174, 1123, 1942, 2709, 1464, 2030, 352, 3921, 3272, 1949, 1950, 3489, 
        427, 2090, 1954, 2499, 941, 730, 3534, 2322, 1960, 1542, 1962, 1963, 541, 1965, 2047, 2177, 
        1927, 1012, 3658, 1971, 2239, 218, 1494, 1511, 1976, 2890, 1978, 1979, 3066, 324, 1982, 955, 
        247, 1310, 1986, 2539, 3046, 1989, 1990, 432, 1992, 1993, 1994, 281, 3608, 2584, 716, 491, 
        3077, 458, 2002, 2119, 2389, 85, 1765, 1829, 2008, 2009, 2010, 2011, 3032, 2013, 2256, 2015, 
        2088, 3351, 1312, 2809, 2020, 2972, 1383, 601, 3812, 834, 1400, 3628, 2028, 75, 2547, 2031, 
        3052, 2033, 1410, 2035, 2097, 2037, 481, 912, 2040, 2041, 2042, 2043, 2044, 2045, 2046, 373, 
        1001, 2049, 1104, 448, 3140, 3853, 2054, 4080, 2056, 490, 496, 393, 2060, 642, 2495, 2063, 
        2865, 2065, 3677, 2392, 2452, 2069, 2070, 2071, 3703, 3502, 2431, 3641, 2076, 2077, 880, 1652, 
        3144, 2081, 2082, 685, 127, 3188, 3452, 1683, 2148, 121, 82, 2083, 3779, 3165, 1673, 2095, 
        2096, 1948, 2098, 1261, 1681, 1943, 2229, 1711, 2162, 2814, 435, 2107, 356, 2126, 2110, 573, 
        3975, 2113, 774, 2328, 2116, 2117, 2118, 1955, 262, 2121, 2122, 2123, 2124, 2125, 1171, 2127, 
        2128, 2672, 2130, 3303, 2132, 2133, 2134, 2135, 1920, 2137, 2138, 2139, 2512, 2141, 2142, 2143, 
        2144, 1379, 2146, 2750, 3556, 2149, 3916, 2151, 2152, 874, 884, 2155, 2156, 867, 3097, 2159, 
        2273, 1285, 1883, 2163, 2732, 1577, 2166, 2628, 2168, 2169, 1578, 2171, 2381, 2173, 9, 2175, 
        3969, 661, 2178, 2778, 2180, 2181, 2182, 1650, 2235, 3170, 3178, 2810, 2188, 2541, 485, 2191, 
        3333, 2193, 3788, 1178, 531, 227, 2198, 644, 3949, 2201, 2202, 2266, 1959, 2339, 1987, 605, 
        141, 2187, 2210, 2936, 1871, 2567, 2296, 3602, 2205, 1931, 2218, 2219, 2220, 444, 2222, 2223, 
        1215, 2225, 2568, 1108, 172, 1505, 402, 3562, 2232, 2468, 88, 976, 3755, 2237, 2238, 2299, 
        2240, 2867, 2184, 2243, 1465, 2245, 2005, 2247, 30, 2249, 2250, 1875, 2252, 2253, 2254, 3146, 
        3908, 3672, 3429, 3151, 1662, 2261, 1353, 777, 1202, 2265, 1103, 2627, 1262, 2269, 2270, 2053, 
        2272, 20, 1926, 2275, 3829, 1964, 2278, 2279, 2941, 2281, 3546, 2283, 2284, 2285, 130, 2287, 
        72, 3967, 2496, 3015, 2292, 2293, 2294, 1254, 50, 2297, 1945, 2606, 2300, 2595, 2302, 2303, 
        2304, 0, 508, 2474, 230, 633, 3034, 2311, 743, 2313, 3426, 2315, 2018, 2603, 3026, 3260, 
        2320, 677, 3021, 2323, 2950, 2325, 683, 2192, 459, 2329, 2330, 2763, 3120, 2333, 401, 588, 
        3713, 2337, 3006, 2136, 2340, 1548, 2406, 251, 2327, 2345, 2346, 2347, 1862, 2482, 473, 3581, 
        568, 2353, 2354, 2356, 1467, 2885, 1026, 2425, 4004, 1804, 2607, 2705, 2364, 2365, 1773, 2084, 
        2368, 2369, 195, 3001, 1435, 1760, 2374, 2375, 2000, 2377, 2378, 893, 2926, 3823, 2982, 2383, 
        2384, 1005, 2386, 2914, 2388, 1764, 2390, 3154, 2109, 2213, 2666, 2395, 2925, 2274, 2724, 169, 
        2400, 3941, 1466, 3749, 3128, 2012, 1341, 3295, 2260, 2902, 2410, 3016, 2412, 3201, 780, 264, 
        1776, 1531, 4095, 2419, 1583, 2469, 2157, 2861, 2424, 45, 2455, 3186, 2619, 2429, 80, 4040, 
        3337, 797, 2434, 4048, 334, 2437, 2264, 3506, 2440, 1102, 2442, 1471, 3067, 3660, 2446, 2447, 
        1049, 322, 2450, 2451, 2212, 1144, 1530, 4025, 2456, 1635, 2656, 2373, 2460, 1089, 2973, 2463, 
        2464, 2465, 3195, 2467, 2477, 2351, 2470, 1921, 2472, 629, 3290, 2358, 2476, 2160, 233, 2453, 
        2480, 2481, 2791, 1540, 561, 2485, 2486, 1961, 2488, 1825, 2490, 2527, 2492, 3200, 3192, 2199, 
        980, 1303, 2308, 4076, 3583, 2501, 2502, 383, 967, 1019, 367, 1481, 1209, 2509, 167, 2511, 
        3686, 2513, 2514, 2515, 3863, 927, 3117, 1293, 2922, 2521, 370, 2523, 1634, 3407, 1869, 660, 
        2589, 2529, 2263, 2531, 1181, 2533, 3934, 257, 2454, 3759, 2966, 1767, 480, 229, 1665, 2543, 
        2544, 2545, 333, 2908, 26, 2549, 309, 1754, 1113, 1969, 3307, 2555, 1655, 2129, 2558, 3253, 
        2560, 841, 3622, 465, 2564, 2565, 549, 1693, 3746, 1571, 3545, 2737, 2004, 1269, 3477, 2575, 
        3227, 2577, 2578, 3043, 2580, 3705, 2150, 2583, 1374, 2585, 2586, 2551, 2588, 3654, 3212, 1940, 
        2048, 2593, 2702, 1475, 3977, 2597, 1440, 2228, 64, 47, 2602, 129, 2604, 1817, 3629, 1090, 
        2608, 3807, 359, 1856, 3580, 1177, 2614, 2615, 2616, 2617, 2554, 3435, 1455, 1958, 248, 2623, 
        2624, 1632, 2626, 171, 71, 3479, 3308, 2631, 885, 2633, 2634, 2635, 3368, 1932, 1067, 1901, 
        2640, 1128, 2642, 1473, 2993, 4063, 2535, 1612, 3688, 2649, 3966, 2651, 2652, 2653, 2216, 1324, 
        1114, 287, 4087, 3993, 2660, 4094, 54, 3266, 2931, 2665, 3474, 2667, 1436, 1988, 483, 2671, 
        337, 2673, 203, 2675, 2068, 2677, 2398, 2679, 2680, 2471, 2682, 341, 1121, 2685, 2686, 3396, 
        3080, 2416, 753, 3094, 2692, 3129, 2522, 2695, 2696, 2697, 2698, 2980, 1692, 2024, 1782, 2703, 
        1644, 2800, 2706, 451, 2708, 3753, 699, 1983, 2027, 2713, 2714, 263, 1120, 2717, 1115, 2719, 
        232, 4055, 2868, 3643, 2006, 662, 2726, 2505, 2062, 2729, 1191, 200, 3057, 828, 2734, 2735, 
        2736, 2991, 182, 2739, 2940, 3585, 3879, 2743, 2744, 2742, 1342, 2747, 1925, 2475, 945, 2751, 
        421, 954, 2754, 2423, 2756, 1487, 2758, 2759, 3717, 2370, 3162, 1712, 2764, 1863, 2766, 2767, 
        2674, 2769, 3220, 4015, 2244, 2773, 3086, 3735, 846, 1414, 3737, 800, 2444, 3349, 3563, 2783, 
        2784, 2753, 2786, 2787, 1368, 2789, 1616, 338, 4023, 2650, 2794, 2795, 2863, 686, 2798, 2799, 
        591, 2801, 1554, 3571, 2804, 23, 1084, 2807, 2808, 3501, 2276, 2165, 3279, 102, 3291, 2815, 
        308, 2153, 4033, 2418, 165, 2821, 2822, 2823, 2824, 2825, 2826, 486, 2271, 3, 302, 2831, 
        3711, 2833, 1687, 2835, 2836, 2837, 2838, 3019, 2536, 2700, 1880, 1423, 4086, 3704, 2846, 2847, 
        1124, 2849, 3588, 2851, 1397, 762, 2493, 2855, 2856, 2857, 2858, 1544, 3310, 2441, 2862, 2572, 
        2864, 1596, 2291, 901, 3382, 2869, 2870, 2752, 97, 1806, 2874, 1432, 1953, 2877, 2878, 3306, 
        657, 2881, 2882, 2883, 2884, 766, 266, 2887, 2888, 2699, 1059, 2891, 2892, 2893, 2894, 2895, 
        2420, 2897, 2093, 3249, 1916, 155, 29, 2903, 208, 2905, 445, 319, 938, 430, 2910, 2911, 
        2912, 2913, 276, 2915, 1737, 1586, 3984, 2919, 1166, 964, 1525, 2436, 3945, 3701, 2654, 3657, 
        2286, 2929, 2930, 168, 2932, 2550, 399, 1627, 2114, 2937, 3875, 3958, 3645, 2309, 3651, 3998, 
        2944, 2380, 2946, 2947, 2934, 735, 3819, 4032, 2952, 2953, 2954, 2955, 2956, 2957, 2958, 1199, 
        3324, 3620, 2962, 3769, 140, 2965, 3473, 2967, 2968, 2969, 407, 3420, 162, 604, 1539, 3682, 
        2976, 2977, 1430, 3736, 714, 2981, 2818, 2983, 2984, 2985, 2986, 2987, 2988, 2348, 3068, 1996, 
        3610, 1013, 3107, 2995, 2099, 2997, 345, 1561, 1647, 410, 3002, 2974, 3459, 3005, 808, 3007, 
        3598, 3009, 996, 4022, 3012, 2359, 2843, 1029, 3638, 206, 3270, 1030, 2832, 1351, 1739, 545, 
        652, 1951, 2850, 3027, 3089, 3029, 3211, 234, 1499, 3033, 818, 3035, 3036, 3928, 3038, 703, 
        881, 2295, 3311, 2478, 3191, 659, 2768, 224, 1438, 813, 104, 3051, 3422, 3414, 3054, 2174, 
        3056, 3913, 3058, 3059, 3347, 235, 1847, 2557, 3669, 3189, 675, 1547, 2961, 237, 2573, 133, 
        2231, 3073, 1233, 978, 3076, 2371, 3078, 2115, 3937, 1299, 2170, 3083, 1002, 620, 2426, 1956, 
        3088, 2209, 3090, 3091, 918, 3093, 830, 953, 3096, 3706, 1602, 3099, 3100, 3265, 3102, 3103, 
        2834, 811, 3106, 3039, 2630, 1282, 3271, 3111, 3112, 2066, 1037, 3115, 2537, 3424, 2255, 1098, 
        152, 207, 2473, 756, 2866, 3125, 1546, 3127, 4021, 3877, 3130, 3167, 2508, 3113, 752, 2479, 
        707, 2443, 3138, 1701, 3574, 3141, 1189, 1797, 695, 2352, 1581, 2349, 776, 3149, 3150, 4019, 
        600, 3153, 1980, 3155, 3156, 1267, 679, 3159, 3160, 455, 613, 3163, 1387, 1004, 3166, 1463, 
        1334, 3169, 274, 928, 3914, 3173, 2664, 1226, 3176, 3177, 1205, 3179, 3636, 2792, 1343, 3183, 
        7, 3185, 3839, 1139, 2103, 973, 1568, 3236, 2516, 3193, 3942, 2197, 3196, 3197, 817, 3199, 
        864, 1512, 17, 3203, 2904, 3205, 2770, 3207, 3208, 3209, 3210, 741, 2277, 3213, 1021, 3095, 
        3216, 2556, 3989, 1541, 3985, 2280, 3222, 2227, 2548, 1562, 1136, 2611, 562, 3229, 312, 1063, 
        3232, 1833, 3234, 3235, 2061, 3237, 3238, 344, 710, 3241, 3242, 488, 3244, 760, 3246, 3247, 
        286, 727, 3250, 3251, 3024, 4081, 3254, 3255, 414, 2579, 290, 3259, 3827, 3261, 2542, 3536, 
        3264, 2738, 759, 3267, 3268, 447, 838, 114, 627, 14, 3274, 651, 3276, 3041, 1557, 968, 
        1311, 3281, 307, 3283, 3284, 3285, 1598, 2394, 3288, 3289, 3553, 3081, 2241, 3293, 1362, 2408, 
        3296, 3938, 3298, 3299, 3300, 2828, 2581, 1360, 3327, 3305, 590, 3217, 3918, 2290, 10, 2435, 
        3312, 3313, 3062, 2945, 1247, 1538, 3318, 888, 3320, 3321, 2248, 3323, 2610, 3325, 3572, 1284, 
        2196, 3564, 1778, 3331, 250, 3214, 3537, 3335, 3336, 3903, 3338, 436, 1057, 1132, 3342, 3343, 
        3344, 2625, 2376, 1998, 3348, 1677, 3350, 923, 3352, 398, 2598, 863, 3356, 3357, 1688, 3258, 
        3360, 347, 848, 1038, 1172, 3365, 1426, 3367, 3384, 1697, 1618, 3371, 653, 3373, 3659, 3375, 
        2765, 3377, 3378, 3379, 249, 3381, 2816, 3383, 3069, 3074, 3386, 3164, 2960, 3389, 3390, 456, 
        3392, 2939, 2566, 2963, 523, 2644, 3398, 3399, 1672, 3401, 3402, 3403, 3416, 1872, 1325, 3263, 
        3466, 1097, 3410, 3411, 3412, 3413, 425, 3415, 2396, 722, 3418, 1656, 608, 3048, 3467, 3423, 
        3137, 3425, 3971, 511, 1162, 2669, 3430, 3431, 3432, 495, 3434, 3893, 3436, 3437, 3354, 2994, 
        28, 2385, 939, 3443, 698, 4047, 3168, 2075, 3448, 1769, 1329, 3451, 189, 2670, 3454, 940, 
        3456, 3457, 3458, 617, 3460, 3461, 3462, 3463, 2525, 746, 1551, 386, 3468, 3469, 3912, 3471, 
        3986, 3861, 3785, 1283, 560, 2785, 3589, 2775, 3480, 1919, 3482, 3483, 3484, 1080, 3433, 160, 
        374, 1416, 3930, 1576, 636, 2362, 3494, 3495, 2432, 3497, 1867, 726, 3000, 2978, 2022, 3503, 
        3504, 1315, 2094, 3341, 859, 3509, 3510, 2288, 3512, 1709, 3514, 3515, 857, 3517, 3518, 3519, 
        3520, 3864, 3522, 778, 3524, 3773, 2979, 3527, 764, 3529, 3530, 3531, 3902, 866, 2587, 2813, 
        2928, 40, 3538, 1437, 3540, 2657, 3542, 3543, 3544, 1770, 3840, 3361, 3548, 3794, 3550, 3551, 
        3552, 2772, 3554, 821, 2007, 2433, 3558, 3605, 3560, 2331, 1985, 3691, 2562, 3565, 3566, 2363, 
        1605, 2927, 3570, 1967, 1375, 3573, 2019, 38, 2484, 3157, 2829, 3579, 3450, 2233, 2844, 1865, 
        3334, 2632, 2662, 1941, 48, 3667, 1433, 3591, 3592, 3593, 3594, 3595, 3813, 3597, 493, 628, 
        3600, 3601, 781, 3603, 611, 2530, 3606, 3696, 693, 126, 343, 2762, 3612, 2214, 3499, 3615, 
        3616, 3617, 1231, 3708, 2830, 3621, 3292, 3623, 1116, 3287, 2379, 3627, 3521, 1447, 3428, 3833, 
        3632, 49, 3634, 3022, 3946, 3637, 958, 3639, 3640, 715, 3642, 2100, 1611, 536, 3646, 3647, 
        3648, 2055, 1981, 2559, 3652, 3653, 1470, 1009, 44, 1346, 3060, 2268, 1349, 470, 3662, 3663, 
        2105, 2780, 3768, 2949, 2643, 3206, 3670, 3671, 2871, 1211, 3098, 3675, 3828, 3108, 1891, 4002, 
        3680, 3555, 3444, 3843, 3684, 533, 2582, 1972, 1669, 3689, 3690, 3500, 3692, 1500, 3694, 2067, 
        1006, 3697, 2242, 1675, 1819, 1802, 2793, 1699, 418, 3355, 623, 547, 2215, 3526, 3710, 3134, 
        2622, 765, 3714, 3715, 1180, 3569, 3718, 3719, 3720, 3721, 3722, 3723, 3724, 3725, 3726, 3727, 
        8, 16, 3730, 3731, 3732, 3742, 3734, 3944, 1646, 882, 3738, 966, 3740, 2853, 1200, 443, 
        1076, 3745, 3269, 3747, 3748, 1399, 1372, 3751, 159, 1229, 3754, 1918, 2430, 2636, 3758, 957, 
        3760, 983, 3762, 3763, 3764, 519, 3561, 3767, 115, 1679, 3486, 609, 1824, 1289, 3774, 3775, 
        1183, 3777, 3778, 158, 3557, 2655, 1691, 3783, 3442, 4000, 2029, 1356, 2405, 3789, 3790, 517, 
        3792, 1826, 2661, 2404, 3796, 3797, 3798, 3695, 3800, 739, 3802, 3931, 3804, 1147, 809, 1479, 
        3808, 3809, 109, 3811, 3838, 959, 3814, 1081, 3816, 3817, 3586, 529, 3820, 574, 3822, 27, 
        619, 3825, 1297, 3387, 610, 2402, 1417, 1852, 3832, 3900, 3834, 3712, 3836, 1251, 24, 694, 
        3894, 3841, 1552, 1624, 552, 1667, 3862, 3847, 1040, 3849, 1620, 3851, 3852, 1717, 3650, 2164, 
        931, 546, 489, 3859, 3860, 3042, 3171, 1975, 4042, 1450, 3866, 3867, 1218, 4059, 3870, 3871, 
        3872, 1610, 3874, 2668, 1092, 2876, 2618, 1730, 3880, 3881, 3882, 3883, 3884, 3885, 1408, 4016, 
        3888, 3889, 3890, 3891, 3322, 2017, 3831, 3895, 3896, 3897, 304, 3899, 1392, 3440, 1048, 98, 
        3064, 3905, 3906, 3907, 2318, 3909, 1361, 3911, 920, 1263, 2332, 3915, 3408, 3917, 1573, 3919, 
        3920, 2258, 3922, 3923, 3924, 3925, 3926, 1492, 602, 3929, 1348, 1721, 3932, 3806, 3957, 1187, 
        3936, 148, 3525, 3939, 3940, 3309, 3784, 3750, 919, 1631, 2312, 2552, 896, 1069, 1394, 1690, 
        3952, 4052, 3954, 3955, 222, 640, 173, 1052, 3960, 2998, 3358, 3963, 11, 3965, 2774, 2806, 
        3968, 412, 3970, 3388, 3972, 3780, 176, 933, 3976, 3121, 3978, 2189, 2681, 3981, 4006, 3983, 
        985, 3676, 3776, 81, 1877, 3795, 3990, 3991, 3992, 3301, 3994, 3995, 3996, 3997, 2336, 3999, 
        4010, 4001, 3528, 1061, 2321, 4005, 3395, 4065, 1260, 2335, 2185, 4011, 4012, 4013, 4014, 948, 
        268, 3699, 1125, 3532, 1508, 2415, 3239, 3233, 520, 3549, 4026, 742, 3231, 4029, 3576, 4031, 
        2140, 1831, 4034, 2701, 2975, 3613, 3393, 4039, 4049, 4041, 2760, 4043, 4044, 4045, 4046, 702, 
        829, 1597, 2106, 2449, 494, 3049, 4054, 2361, 624, 4057, 2723, 1290, 4060, 4061, 2845, 899, 
        4064, 3346, 134, 4067, 1731, 988, 4070, 4071, 4072, 4073, 1886, 4075, 3316, 1270, 1047, 1740, 
        3493, 2746, 4082, 280, 299, 3854, 2899, 3846, 3225, 4089, 4090, 4091, 1452, 4093, 2854, 4037, 
    };
    unsigned long test_array_len = sizeof(test_array) / sizeof(unsigned long);
    
    unsigned long buckets_num = HASH_BUCKET_NUM;
    struct hlist_head *h_buckets =  \
        malloc(sizeof(struct hlist_head) * buckets_num);
    if (h_buckets == NULL) {
        LOG_TEST_FAIL("failed to allocate memory for hash buckets!\n");
    }
    struct hash_table *htab = init_hash_table(
        malloc(sizeof(struct hash_table)),
        h_buckets,
        buckets_num,
        &__htab_opts
    );
    if (htab == NULL) {
        LOG_TEST_FAIL("failed to create hash table!\n");
    }
    char *in_table_marks = malloc(sizeof(char) * test_array_len);
    if (in_table_marks == NULL) {
        LOG_TEST_FAIL("failed to allocate memory for marking in-table elemtns!\n");
    } else {
        memset(in_table_marks, 0, sizeof(char) * test_array_len);
    }
    char *tmp_in_table_marks = malloc(sizeof(char) * test_array_len);
    if (tmp_in_table_marks == NULL) {
        LOG_TEST_FAIL("failed to allocate memory for marking in-table elemtns!\n");
    }

    /// 开始测试。
    unsigned long cnt = 0;
    unsigned long first_insert = 512;
    unsigned long in_out_nums = 256;
    int ret;

    /// 进行首次插入。
    for (cnt = 0; cnt < first_insert; cnt++) {
        ret = insert_one_key(
            htab, 
            in_table_marks, 
            test_array[cnt], 
            test_array_len, 
            0
        );
        if (ret != 0) {
            break;
        } 
    }
    if (cnt == first_insert) {
        LOG_TEST_PASS("first insertion succeeded! htab->nums: %lu\n", htab->nums);
    }

    /// 删除和插入元素测试。
    for (cnt = cnt; cnt < test_array_len; cnt += in_out_nums) {
        unsigned long cnt1 = 0;
        for (cnt1 = 0; cnt1 < in_out_nums; cnt1++) {
            ret = insert_one_key(
                htab, 
                in_table_marks, 
                test_array[cnt + cnt1], 
                test_array_len, 
                0
            );
            if (ret != 0) {
                break;
            } 
        }
        if (cnt1 != in_out_nums) {
            break;
        }
        ret = validate_hash_table(
            htab,
            test_array,
            test_array_len,
            in_table_marks
        );
        if (ret != 0) {
            break;
        } 

        for (cnt1 = 0; cnt1 < in_out_nums; cnt1++) {
            ret = delete_one_key(
                htab, 
                in_table_marks, 
                test_array[cnt + cnt1 - first_insert], 
                test_array_len
            );
            if (ret != 0) {
                break;
            } 
        }
        ret = validate_hash_table(
            htab,
            test_array,
            test_array_len,
            in_table_marks
        );
        if (ret != 0) {
            break;
        } 
    }

    if (cnt == test_array_len) {
        LOG_TEST_PASS("insertion and deletion succeeded! htab->nums: %lu\n", htab->nums);
    }

    ret = foreach_hash_node_test(
        htab, test_array_len, tmp_in_table_marks, in_table_marks
    );
    if (!ret) {
        LOG_TEST_PASS("foreach_hash_node_test\n");
    }

    /// 重复插入测试。
    for (cnt -= first_insert; cnt < test_array_len; cnt++) {
        ret = insert_one_key(
            htab, 
            in_table_marks, 
            test_array[cnt], 
            test_array_len, 
            1
        );
        if (ret != 0) {
            break;
        } 
        ret = validate_hash_table(
            htab,
            test_array,
            test_array_len,
            in_table_marks
        );
        if (ret != 0) {
            break;
        } 
    }
    if (cnt == test_array_len) {
        LOG_TEST_PASS("multitime insertion succeeded! htab->nums: %lu\n", htab->nums);
    }

    ret = foreach_hash_node_test(
        htab, test_array_len, tmp_in_table_marks, in_table_marks
    );
    if (!ret) {
        LOG_TEST_PASS("foreach_hash_node_test\n");
    }

    /// 全部删除
    for (cnt -= first_insert; cnt < test_array_len; cnt++) {
        ret = delete_one_key(
            htab, 
            in_table_marks, 
            test_array[cnt], 
            test_array_len
        );
        if (ret != 0) {
            break;
        } 
        ret = validate_hash_table(
            htab,
            test_array,
            test_array_len,
            in_table_marks
        );
        if (ret != 0) {
            break;
        } 
    }
    if (cnt == test_array_len) {
        LOG_TEST_PASS("multitime insertion succeeded! htab->nums: %lu\n", htab->nums);
    }

    ret = foreach_hash_node_test(
        htab, test_array_len, tmp_in_table_marks, in_table_marks
    );
    if (!ret) {
        LOG_TEST_PASS("foreach_hash_node_test\n");
    }

    free(in_table_marks);
    free(tmp_in_table_marks);
    free(htab);
    free(h_buckets);
}
